package class5;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.ArrayList;
import java.util.List;

public class Code10_hasPathSumII {

    public static void main(String[] args) {
        TreeNode treeNode = getTreeNode();
        List<List<Integer>> b = pathSum(treeNode, 22);
        System.out.println("b = " + b);

    }

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        process(root, path, 0, sum, ans);
        return ans;
    }

    /**
     * @param x
     * @param path
     * @param preSum
     * @param sum
     * @param ans
     */
    public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
        if (x.left == null && x.right == null) {
            if (x.val + preSum == sum) {
                path.add(x.val);
                ans.add(copy(path));
                // 清理现场用，删除当前节点
                path.remove(path.size() - 1);
            }
            return;
        }

        // 非叶节点
        preSum += x.val;
        path.add(x.val);
        if (x.left != null) {
            process(x.left, path, preSum, sum, ans);
        }
        if (x.right != null) {
            process(x.right, path, preSum, sum, ans);
        }
        path.remove(path.size() - 1);
    }

    public static List<Integer> copy(List<Integer> path) {
        List<Integer> ans = new ArrayList();
        for (Integer i : path) {
            ans.add(i);
        }
        return ans;
    }

    private static TreeNode getTreeNode() {
        /**
         *       5
         *     /   \
         *    4     8
         *   11    13 4
         *  7  2       1
         */

        TreeNode root = TreeNodeUtils.createTreeNode(5, 4, 8);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(11, 13, 4);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(7, 2, 1);

        thr[0].left = foth[0];
        thr[0].right = foth[1];
        thr[2].right = foth[2];
        root.left.left = thr[0];
        root.right.left = thr[1];
        root.right.right = thr[2];
        return root;
    }
}
